The tenacity of a graph G, T(G), is de ned by T(G) = minfjSj+ (G S)! (G S) g, where the minimum is taken over all vertex cutsets S of G. We de ne (G S) to be the number of the vertices in the largest component of the graph G S, and! (G S) be the number of components of G S. In this paper we consider the relationship between the minimum degree (G) of a graph and the complexity of recognizing if a graph is T-tenacious. Let T 1 be a rational number. We rst show that if (G) Tn T+1, then G is T-tenacious. On the other hand, for any xed > 0, we show that it is NP-Hard to determine if G is T-tenacious, even for the class of graphs with (G) ( T T+1 )n.